home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Source Code / C / Applications / MacWT 0.9 / wt Source / render.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-10-10  |  42.0 KB  |  1,575 lines  |  [TEXT/CWIE]
  1. /*
  2. **  MacWT -- a 3d game engine for the Macintosh
  3. **  © 1995, Bill Hayden and Nikol Software
  4. **  Free for non-commercial use - address questions to the e-mail address below
  5. **
  6. **  Mail:           afn28988@freenet.ufl.edu (Bill Hayden)
  7. **    MacWT FTP site: ftp.circa.ufl.edu/pub/software/ufmug/mirrors/LocalSW/Hayden/
  8. **  WWW Page:       http://grove.ufl.edu:80/~nikolsw
  9. **
  10. **    All of the above addresses are due to changes sometime in 1996, so stay tuned
  11. **
  12. **  based on wt, by Chris Laurel
  13. **
  14. **  This program is distributed in the hope that it will be useful,
  15. **  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16. **  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  17. */
  18.  
  19.  
  20. #include <math.h>
  21. #include <stdlib.h>
  22. #include <string.h>
  23. #include "wt.h"
  24. #include "error.h"
  25. #include "fixed.h"
  26. #include "wtmem.h"
  27. #include "table.h"
  28. #include "view.h"
  29. #include "framebuf.h"
  30. #include "texture.h"
  31. #include "list.h"
  32. #include "world.h"
  33. #include "render.h"
  34. #include "object.h"
  35. #include "MacWT.h"
  36. #include "graphics.h"
  37.  
  38.  
  39. /* These macros convert 16.16 fixed point numbers to and from a 2.30 format.
  40. **   The extra fractional precision is needed when doing doing 1 / distance
  41. **   calculations for perspective.
  42. */
  43. #define TO_FIX_2_30(f)   ((f) << 14)
  44. #define FROM_FIX_2_30(f) ((f) >> 14) 
  45. #define TO_FIX_8_24(f)   ((f) << 8)
  46. #define FROM_FIX_8_24(f) ((f) >> 8)
  47.  
  48. #define MAX_WALL_EVENTS 30
  49.  
  50. #define MAX_ERROR  view_width
  51.  
  52.  
  53. typedef struct {
  54.      Wall *wall;
  55.      fixed z, dz;
  56.      Boolean is_back_view;
  57. } Wall_start;
  58.  
  59. typedef Wall *Wall_end;
  60.  
  61. typedef struct {
  62.      int n_events;
  63.      Wall_start events[MAX_WALL_EVENTS];
  64. } Wall_start_list;
  65.  
  66. typedef struct {
  67.      int n_events;
  68.      Wall_end events[MAX_WALL_EVENTS];
  69. } Wall_end_list;
  70.  
  71. typedef struct {
  72.      Boolean is_back_view;
  73.      Wall *wall;
  74.      Boolean visible;
  75.      fixed pstart1, pend1, pstart2, pend2;
  76.      fixed dpstart1, dpend1, dpstart2, dpend2;
  77.      fixed z;
  78.      fixed dz;
  79. } Active_wall;
  80.  
  81. typedef struct {
  82.      fixed pstart1, pend1, pstart2, pend2;
  83.      Boolean is_back_view;
  84.      fixed top, bottom;
  85.      Region *front, *back;
  86.      Wall *wall;
  87.      fixed z;
  88. } Wall_intersection;
  89.  
  90. /*** typedefs for object event lists ***/
  91.  
  92. typedef struct {
  93.      Object *o;
  94.      fixed z;
  95.      fixed first_slice;
  96. } Object_start;
  97.  
  98. typedef Object *Object_end;
  99.  
  100. #define MAX_OBJECT_EVENTS 10
  101. typedef struct {
  102.      int n_events;
  103.      Object_start events[MAX_OBJECT_EVENTS];
  104. } Object_start_list;
  105.  
  106. typedef struct {
  107.      int n_events;
  108.      Object_end events[MAX_OBJECT_EVENTS];
  109. } Object_end_list;
  110.  
  111. typedef struct {
  112.      Object *o;
  113.      fixed x, dx;
  114.      fixed z;
  115. } Active_object;
  116.  
  117. /***/
  118.  
  119. typedef struct {
  120.      fixed screen_dy, screen_dx;
  121.      fixed view_sin, view_cos;
  122.      fixed sin_dx, cos_dx;
  123.      fixed *sin_tab, *cos_tab, *row_view;
  124. } View_constants;
  125.  
  126.  
  127. static void transform_vertices(World *w, View *view);
  128. static void clip_walls(World *w, View *v);
  129. static void add_wall_events(View *v, Wall *wall, fixed x1, fixed px1, fixed x2, fixed px2);
  130. static void render_walls(World *w, View *v);
  131. static int add_events(Active_wall *active, int n_active, int column);
  132. static Boolean wall_obscured(Vertex *common, Vertex *v1, Vertex *v2);
  133. static int remove_events(Active_wall *active, int n_active, int column);
  134. static void add_objects(World *w, View *v);
  135. static int add_obj_events(Active_object *active, int n_active, int column);
  136. static int remove_obj_events(Active_object *active, int n_active, int column);
  137. static void draw_object(Object *o, fixed z, int tex_column, View *v, int fb_column);
  138. static void draw_floors(Wall_intersection *int_list, View *v, int column);
  139. static void draw_floor_slices(Region *r, fixed start, fixed end, View *v, int column);
  140. static void draw_ceiling_slices(Region *r, fixed start, fixed end, View *v, int column);
  141. static fixed wall_ray_intersection(fixed Vx, fixed Vy, Wall *wall);
  142. static void calc_view_constants(View *v, short screen_width, short screen_height);
  143.  
  144. static void do_walls(Active_wall *active, int n_active,
  145.              Active_object *active_obj, int n_active_obj,
  146.              int column, View *v, fixed Vx, fixed Vy);
  147.  
  148.  
  149.  
  150.  
  151. static Framebuffer *fb = NULL;
  152.  
  153. static Wall_start_list        *start_events = NULL;
  154. static Wall_end_list        *end_events = NULL;
  155. static Wall_intersection    *intersections = NULL;
  156. static Wall_intersection    *cur_slice;
  157. static Object_start_list    *obj_start_events = NULL;
  158. static Object_end_list        *obj_end_events   = NULL;
  159.  
  160. static int                    *fb_rows = NULL;
  161. static short                view_width, view_height;
  162. static View_constants        view_constants;
  163.  
  164.  
  165. #include "slice.c"
  166.  
  167.  
  168. void InitRenderer(short fb_width, short fb_height)
  169. {
  170.     short i;
  171.  
  172.  
  173.     if (fb != NULL)
  174.         wtfree(fb);
  175.     if (start_events != NULL)
  176.         wtfree(start_events);
  177.     if (end_events != NULL)
  178.         wtfree(end_events);
  179.     if (fb_rows != NULL)
  180.         wtfree(fb_rows);
  181.  
  182.     fb = NewFramebuffer(fb_width, fb_height);
  183.     start_events = (Wall_start_list *)wtmalloc(sizeof(Wall_start_list) * (fb_width + 1));
  184.     end_events = (Wall_end_list *)wtmalloc(sizeof(Wall_end_list) * (fb_width + 1));
  185.     obj_start_events = (Object_start_list *)wtmalloc(sizeof(Object_start_list) * (fb_width + 1));
  186.     obj_end_events   = (Object_end_list *)wtmalloc(sizeof(Object_end_list) * (fb_width + 1));
  187.  
  188.     fb_rows = (int *)wtmalloc(sizeof(int) * fb_height);
  189.     
  190.     fb->fb_rbytes = GetRowBytes() / gSizeOfPixel;
  191.     for (i = 0; i < fb_height; i++)
  192.         fb_rows[i] = i * fb_width;
  193.  
  194.     view_width = fb->fb_width;
  195.     view_height = fb->fb_height;
  196. }
  197.  
  198.  
  199.  
  200. void    Render(World *w, View *v)
  201. {
  202.     short i;
  203.  
  204.     for (i = 0; i <= view_width; i++)    // Initialize buffers
  205.         {
  206.         start_events[i].n_events = 0;
  207.         end_events[i].n_events = 0;
  208.         obj_start_events[i].n_events = 0;
  209.         obj_end_events[i].n_events = 0;
  210.         }
  211.  
  212.     calc_view_constants(v, view_width, view_height);
  213.     transform_vertices(w, v);
  214.     clip_walls(w, v);
  215.     add_objects(w, v);
  216.     ClearFramebuffer(fb);
  217.     render_walls(w, v);
  218. }
  219.  
  220.  
  221.  
  222. static void transform_vertices(World *w, View *view)
  223. {
  224.     Vertex *vertex;
  225.     fixed view_sin, view_cos;
  226.     short i;
  227.  
  228.  
  229.     vertex = TABLE_ELEMENTS(w->vertices, Vertex);
  230.     view_sin = view_constants.view_sin;
  231.     view_cos = view_constants.view_cos;
  232.  
  233.     for (i = 0; i < TABLE_SIZE(w->vertices); i++, vertex++)
  234.         {
  235.         fixed x = vertex->x - view->x;
  236.         fixed y = vertex->y - view->y;
  237.  
  238.         vertex->tx = fixmul(x, view_cos) - fixmul(y, view_sin);
  239.         vertex->ty = fixmul(x, view_sin) + fixmul(y, view_cos);
  240.         if (vertex->tx > view->eye_distance)
  241.            /* project point onto view plane */
  242.             vertex->proj = fixdiv(vertex->ty, vertex->tx);
  243.          }
  244. }
  245.  
  246.  
  247.  
  248. static void clip_walls(World *w, View *v)
  249. {
  250.     Wall *wall = (Wall *) w->walls->table;
  251.     short i;
  252.  
  253.     for (i = 0; i < TABLE_SIZE(w->walls); i++, wall++)
  254.         {
  255.         fixed x1, y1, px1, x2, y2, px2;
  256.         unsigned int outcode1, outcode2;
  257.  
  258.         x1 = wall->vertex1->tx;
  259.         x2 = wall->vertex2->tx;
  260.         /* See if the wall lies completely behid the view plane. */
  261.         if (x1 < v->eye_distance && x2 < v->eye_distance)
  262.             continue;
  263.  
  264.         y1 = wall->vertex1->ty;
  265.         px1 = wall->vertex1->proj;
  266.         y2 = wall->vertex2->ty;
  267.         px2 = wall->vertex2->proj;
  268.  
  269.             /*** Clipping ***/
  270.  
  271.         /* First, clip to the view plane (line, really, since we're
  272.         **   working in only two dimensions.)
  273.         */
  274.         if (x1 <= v->eye_distance)
  275.             {
  276.            /* be careful for division overflow */
  277.             if (x2 - x1 < FIXED_EPSILON)
  278.                 continue;
  279.             y1 = y1 + fixmul(v->eye_distance - x1, fixdiv(y2 - y1, x2 - x1));
  280.             px1 = y1;
  281.             x1 = v->eye_distance;
  282.             }
  283.  
  284.         if (x2 <= v->eye_distance)
  285.             {
  286.             if (x1 - x2 < FIXED_EPSILON)
  287.                 continue;
  288.             y2 = y2 + fixmul(v->eye_distance - x2, fixdiv(y1 - y2, x1 - x2));
  289.             px2 = y2;
  290.             x2 = v->eye_distance;
  291.             }
  292.  
  293.         /* Now, clip to the sides of the view polygon. */
  294.         outcode1 = FIXED_SIGN(v->view_plane_size + px1);
  295.         outcode1 |= FIXED_SIGN(v->view_plane_size - px1) << 1;
  296.         outcode2 = FIXED_SIGN(v->view_plane_size + px2);
  297.         outcode2 |= FIXED_SIGN(v->view_plane_size - px2) << 1;
  298.  
  299.         /* trivial reject */
  300.         if ((outcode1 & outcode2) != 0)
  301.             continue;
  302.             
  303.         /* check for trivial accept */
  304.         if ((outcode1 | outcode2) != 0)
  305.             {
  306.             /* We need to clip. */
  307.             fixed base_slope, slope, denom, y_diff;
  308.  
  309.             denom = (x2 - x1);
  310.             if (FIXED_ABS(denom) < FIXED_EPSILON)
  311.                 {
  312.                 if (denom < 0)
  313.                     base_slope = FIXED_MIN + v->view_plane_size;
  314.                 else
  315.                     base_slope = FIXED_MAX - v->view_plane_size;
  316.                 }
  317.             else
  318.                 base_slope = fixdiv(y2 - y1, denom);
  319.  
  320.             if (outcode1 == 1)
  321.                 {
  322.                 px1 = -v->view_plane_size;
  323.                 y_diff = y1 - fixmul(x1, -v->view_plane_size);
  324.                 slope = base_slope + v->view_plane_size;
  325.                 if (FIXED_ABS(slope) > FIXED_EPSILON)
  326.                     x1 -= fixdiv(y_diff, slope);
  327.                 else
  328.                     x1 = FIXED_MAX;
  329.             }
  330.         else if (outcode1 == 2)
  331.             {
  332.             px1 = v->view_plane_size;
  333.             y_diff = y1 - fixmul(x1, v->view_plane_size);
  334.             slope = base_slope - v->view_plane_size;
  335.             if (FIXED_ABS(slope) > FIXED_EPSILON)
  336.                 x1 -= fixdiv(y_diff, slope);
  337.             else
  338.                 x1 = FIXED_MAX;
  339.            }
  340.  
  341.         if (outcode2 == 1)
  342.             {
  343.             px2 = -v->view_plane_size;
  344.             y_diff = y2 - fixmul(x2, -v->view_plane_size);
  345.             slope = base_slope + v->view_plane_size;
  346.             if (FIXED_ABS(slope) > FIXED_EPSILON)
  347.                 x2 -= fixdiv(y_diff, slope);
  348.             else
  349.                 x2 = FIXED_MAX;
  350.             }
  351.         else if (outcode2 == 2)
  352.             {
  353.             px2 = v->view_plane_size;
  354.             y_diff = y2 - fixmul(x2, v->view_plane_size);
  355.             slope = base_slope - v->view_plane_size;
  356.             if (FIXED_ABS(slope) > FIXED_EPSILON)
  357.                 x2 -= fixdiv(y_diff, slope);
  358.             else
  359.                 x2 = FIXED_MAX;
  360.             }
  361.         }
  362.  
  363.     add_wall_events(v, wall, x1, px1, x2, px2);
  364.     }
  365. }
  366.  
  367.  
  368. /* Add a wall to the event list--one event is added for the start of the
  369. **   wall, and another is added to mark the end of the wall.
  370. */
  371. static void add_wall_events(View *v, Wall *wall, fixed x1, fixed px1, fixed x2, fixed px2)
  372. {
  373.     int fb1, fb2;
  374.     fixed z1, z2;
  375.     Wall_start *event;
  376.  
  377.  
  378.     /* convert to frame buffer coordinates */
  379.     px1 = fixdiv(px1, view_constants.screen_dx + 1);
  380.     px2 = fixdiv(px2, view_constants.screen_dx + 1);
  381.     fb1 = FIXED_TO_INT(px1) + (view_width >> 1);
  382.     fb2 = FIXED_TO_INT(px2) + (view_width >> 1);
  383.  
  384.     /* There's no need to deal with walls that start and end in the same
  385.     **   screen column.  In a properly contructed world, we're guaranteed
  386.     **   that throwing them away won't leave any gaps.
  387.     */
  388.     if (fb1 == fb2)
  389.         return;
  390.  
  391.     /* Here we use a 2.30 fixed point format.  The result of this calculation
  392.     **   is always between 1 and zero, as the distance can never be less
  393.     **   than the view plane distance.  The extra fractional bits are
  394.     **   critical for the inverses.  Note that using 2.30 restricts the
  395.     **   size of the view plane to something less than 2.
  396.     */
  397.     z1 = fixdiv(TO_FIX_2_30(v->eye_distance), x1);
  398.     z2 = fixdiv(TO_FIX_2_30(v->eye_distance), x2);
  399.  
  400.     if (fb1 < fb2)
  401.         {
  402.         event = &start_events[fb1].events[start_events[fb1].n_events];
  403.  
  404.         event->wall = wall;
  405.         event->z = z1;
  406.         event->dz = fixdiv(z2 - z1, INT_TO_FIXED(fb2 - fb1));
  407.         event->is_back_view = FALSE;
  408.         start_events[fb1].n_events++;
  409.  
  410.         end_events[fb2].events[end_events[fb2].n_events] = wall;
  411.         end_events[fb2].n_events++;
  412.         }
  413.     else
  414.         {
  415.         event = &start_events[fb2].events[start_events[fb2].n_events];
  416.  
  417.         event->wall = wall;
  418.         event->z = z2;
  419.         event->dz = fixdiv(z1 - z2, INT_TO_FIXED(fb1 - fb2));
  420.         event->is_back_view = TRUE;
  421.         start_events[fb2].n_events++;
  422.  
  423.         end_events[fb1].events[end_events[fb1].n_events] = wall;
  424.         end_events[fb1].n_events++;
  425.         }
  426. }
  427.  
  428.  
  429. static void render_walls(World *w, View *v)
  430. {
  431.     static int last_wall_count = 0;
  432.     static Active_wall *active;
  433.     static Active_object *active_obj;
  434.     int column;
  435.     int active_count = 0, active_obj_count = 0;
  436.     fixed Vx, Vy, dVy;
  437.  
  438.  
  439.      /* Make sure that the active list is large enough to hold all the
  440.      **   walls in a world.
  441.      */
  442.     if (last_wall_count != TABLE_SIZE(w->walls))
  443.         {
  444.         last_wall_count = TABLE_SIZE(w->walls);
  445.         if (active == NULL)
  446.             active = (Active_wall *)wtmalloc(sizeof(Active_wall) * last_wall_count);
  447.         else
  448.             active = (Active_wall *)wtrealloc(active, sizeof(Active_wall) * last_wall_count);
  449.  
  450.         /* I know this is really cheesy, but . . . */
  451.         if (intersections == NULL)
  452.             intersections = (Wall_intersection *)wtmalloc(sizeof(Wall_intersection) * 3000);
  453.         else
  454.             intersections = (Wall_intersection *)
  455.                                 wtrealloc(intersections, sizeof(Wall_intersection) * 4000);
  456.         }
  457.  
  458.     /* Set up for fast calculation of view rays. */
  459.     Vx = v->eye_distance;
  460.     Vy = -v->view_plane_size;
  461.     dVy = fixdiv(fixmul(v->view_plane_size, INT_TO_FIXED(2)), INT_TO_FIXED(view_width));
  462.  
  463.     /* Build a sorted wall intersection list for each screen column. */
  464.     cur_slice = intersections;
  465.  
  466.     for (column = 0; column < view_width; column++)
  467.         {
  468.         Active_wall        *current, *last;
  469.         Active_object    *current_obj, *last_obj;
  470.       /* Keep track of distances of walls in the active list.  Notice that
  471.       **   we're not actually tracking the distances of walls, but 
  472.       **   1 / distance instead.  That's because we can linearly
  473.       **   interpolate 1 / distance.  Also, most calculations that
  474.       **   use distance are really using 1 / distance (i.e. distance
  475.       **   appears in the denominator.
  476.       */
  477.             
  478.         active_count = add_events(active, active_count, column);
  479.         active_obj_count = add_obj_events(active_obj, active_obj_count, column);
  480.  
  481.         do_walls(active, active_count, active_obj, active_obj_count, column, v, Vx, Vy);
  482.         
  483.         active_count = remove_events(active, active_count, column);
  484.         active_obj_count = remove_obj_events(active_obj, active_obj_count, column);
  485.  
  486.         last = active + active_count - 1;
  487.         for (current = active; current <= last; current++)
  488.             {
  489.             current->z += current->dz;
  490.             if (current->visible)
  491.                 {
  492.                 current->pstart1 += current->dpstart1;
  493.                 current->pend1 += current->dpend1;
  494.                 current->pstart2 += current->dpstart2;
  495.                 current->pend2 += current->dpend2;
  496.                 }
  497.             }
  498.             
  499.         last_obj = active_obj + active_obj_count;
  500.         for (current_obj = active_obj; current_obj < last_obj; current_obj++)
  501.             current_obj->x += current_obj->dx;
  502.  
  503.         Vy += dVy;
  504.         }
  505.  
  506.      /* Once we have the per-column sorted intersection list, most of the
  507.      **   tricky stuff is done.  All that's left is to actually blast bytes
  508.      **   into the framebuffer using the routines in slice.c.
  509.      */
  510.     
  511.     if (gDrawFC)
  512.         draw_floors(intersections, v, 0);
  513. }
  514.  
  515.  
  516. /* Add new walls to the active list.  The active list is kept
  517. **   depth sorted.  We have to be careful here.  Correct depth
  518. **   ordering of the walls is vital for rendering.  At corners
  519. **   we have two or more walls at the same distance; however,
  520. **   there is still a correct and incorrect ordering.  If one
  521. **   wall is obscured by another, the visible wall must be placed
  522. **   in front in the list.
  523. */
  524. static int add_events(Active_wall *active, int n_active, int column)
  525. {
  526.     int i, j;
  527.     Wall_start *event;
  528.     Wall *wall;
  529.     fixed z;
  530.  
  531.     for (i = 0; i < start_events[column].n_events; i++)
  532.         {
  533.         event = start_events[column].events + i;
  534.  
  535.         wall = event->wall;
  536.         z = event->z;
  537.  
  538.         for (j = 0; j < n_active; j++)
  539.             {
  540.             Wall *wall2 = active[j].wall;
  541.             Vertex *common, *v1, *v2;
  542.  
  543.             if (z < active[j].z - MAX_ERROR)
  544.                 continue;
  545.             else if (z > active[j].z + MAX_ERROR)
  546.                 break;
  547.  
  548.            // See if the walls share a vertex.
  549.            
  550.             if (wall->vertex1 == wall2->vertex1)
  551.                 {
  552.                 common = wall->vertex1;
  553.                 v1 = wall->vertex2;
  554.                 v2 = wall2->vertex2;
  555.                 }
  556.             else if (wall->vertex1 == wall2->vertex2)
  557.                 {
  558.                 common = wall->vertex1;
  559.                 v1 = wall->vertex2;
  560.                 v2 = wall2->vertex1;
  561.                 }
  562.             else if (wall->vertex2 == wall2->vertex1)
  563.                 {
  564.                 common = wall->vertex2;
  565.                 v1 = wall->vertex1;
  566.                 v2 = wall2->vertex2;
  567.                 }
  568.             else if (wall->vertex2 == wall2->vertex2)
  569.                 {
  570.                 common = wall->vertex2;
  571.                 v1 = wall->vertex1;
  572.                 v2 = wall2->vertex1;
  573.                 }
  574.             else
  575.                 {
  576.                 /* We have two walls which are really close
  577.                 **   together, but share no vertices.  Because
  578.                 **   of roundoff error, we don't know for certain
  579.                 **   which one is really in front.  Ideally, this
  580.                 **   situation will be avoided by creating worldfiles
  581.                 **   which don't place non-adjoining walls extremely
  582.                 **   close together.
  583.                 */
  584.                 if (z > active[j].z)
  585.                     break;
  586.                 else
  587.                     continue;
  588.                 }
  589.  
  590.             if (!wall_obscured(common, v1, v2) && wall_obscured(common, v2, v1))
  591.                 break;
  592.             }
  593.  
  594.         // Insert the wall into the active list.
  595.         memmove(active + j + 1, active + j, sizeof(Active_wall) * (n_active - j));
  596.         active[j].wall = wall;
  597.         active[j].z = z;
  598.         active[j].dz = event->dz;
  599.         active[j].visible = FALSE;
  600.         active[j].is_back_view = event->is_back_view;
  601.         n_active++;
  602.         }
  603.  
  604.     return n_active;
  605. }
  606.  
  607.  
  608. /* Determine whether wall 1 is obscured by wall 2 from the view point.
  609. **   This will be the case if a halfplane defined by wall 1 contains both the
  610. **   view point and wall 2.  Wall 1 is defined by the points common and v1;
  611. **   wall2 is defined by command and v2.  Note that this function uses the
  612. **   transformed coordinates of the vertices, so the view point and view
  613. **   direction need not be passed explicitly.
  614. */
  615. static Boolean wall_obscured(Vertex *common, Vertex *v1, Vertex *v2)
  616. {
  617.      fixed x1, y1, x2, y2;
  618.      unsigned int sign1, sign2;
  619.  
  620.  
  621.      x1 = common->tx - v1->tx;
  622.      y1 = common->ty - v1->ty;
  623.      x2 = common->tx - v2->tx;
  624.      y2 = common->ty - v2->ty;
  625.  
  626.      /* There's some tricky stuff done here to try to find the signs of
  627.      **   cross products without actually doing any multiplication.  I'm
  628.      **   really not sure if avoiding a few multiplies is worth the extra
  629.      **   overhead of sign checking, but the profiler shows this function as
  630.      **   taking a surprisingly small percentage of execution time.
  631.      */
  632.     if (FIXED_PRODUCT_SIGN(x1, y2) ^ FIXED_PRODUCT_SIGN(x2, y1))
  633.         sign1 = FIXED_PRODUCT_SIGN(x1, y2);
  634.     else
  635.         sign1 = FIXED_SIGN(fixmul(x1, y2) - fixmul(x2, y1));
  636.         
  637.     if (FIXED_PRODUCT_SIGN(x1, common->ty) ^ FIXED_PRODUCT_SIGN(common->tx, y1))
  638.         sign2 = FIXED_PRODUCT_SIGN(x1, common->ty);
  639.     else
  640.         sign2 = FIXED_SIGN(fixmul(x1, common->ty) - fixmul(common->tx, y1));
  641.      
  642.     //return !(sign1 ^ sign2);
  643.     return (sign1 == sign2);
  644. }
  645.  
  646.  
  647.  
  648. // Remove walls from the active list.  Return the number of remaining active walls.
  649.  
  650. static int remove_events(Active_wall *active, int n_active, int column)
  651. {
  652.     int i, j;
  653.     Wall *wall;
  654.  
  655.  
  656.     // This is really inefficient, so I hope these event lists are small.
  657.  
  658.     for (i = 0; i < end_events[column].n_events; i++)
  659.         {
  660.         wall = end_events[column].events[i];
  661.  
  662.         for (j = 0; j < n_active && active[j].wall != wall; j++);
  663.         n_active--;
  664.         memmove(active + j, active + j + 1, sizeof(Active_wall) * (n_active - j));
  665.         }
  666.  
  667.     return n_active;
  668. }
  669.  
  670.  
  671.  
  672.  
  673.  
  674. static void draw_floors(Wall_intersection *int_list, View *v, int column)
  675. {
  676.     Wall_intersection *last, *current;
  677.     Wall_intersection *save_current, *save_last;
  678.     fixed start, end;
  679.     fixed max_floor, min_ceiling;
  680.     fixed last_max_floor = FIXED_ZERO, last_min_ceiling = FIXED_ZERO;
  681.  
  682.  
  683.     last = current = int_list;
  684.  
  685.     for (column = 1; column < view_width; column++)
  686.         {
  687.         for (; current->wall != NULL; current++);
  688.         save_current = ++current;
  689.         save_last = last;
  690.  
  691.       /* get the highest floor and lowest ceiling */
  692.         while (current->wall != NULL)
  693.            current++;
  694.         max_floor = current->bottom;
  695.         min_ceiling = current->top;
  696.  
  697.         current = save_current;
  698.             
  699.       /* draw floors */
  700.         while (last->wall != NULL && current->wall != NULL)
  701.             {
  702.             if (current->front == last->front)
  703.                 start = MAX(last->bottom, current->pstart1);
  704.             else
  705.                 start = MAX(last->bottom, current->bottom);
  706.             end = MIN(last->pstart1, current->pend1);
  707.  
  708.             if (start < end)
  709.                 draw_floor_slices(last->front, start, end, v, column - 1);
  710.  
  711.             if (last->pend1 < current->pend1)
  712.                 last++;
  713.             else
  714.                 current++;
  715.             }
  716.  
  717.       /* draw ceiling slices generated by ceiling walls */
  718.         last = save_last;
  719.         current = save_current;
  720.         while (last->wall != NULL && current->wall != NULL)
  721.             {
  722.             if (current->front == last->front)
  723.                 end = MIN(last->top, current->pend2);
  724.             else
  725.                 end = MIN(last->top, current->top);
  726.             start = MAX(last->pend2, current->pstart2);
  727.  
  728.             if (start < end)
  729.                 draw_ceiling_slices(last->front, start, end, v, column - 1);
  730.  
  731.             if (last->pstart2 > current->pstart2)
  732.                 last++;
  733.             else
  734.                 current++;
  735.             }
  736.  
  737.       /* draw ceiling slices generated by floor walls */
  738.         while (last->wall != NULL)
  739.             {
  740.             start = MAX(last_max_floor, last->pend2);
  741.             end = MIN(max_floor, last->top);
  742.             if (start < end)
  743.                 draw_ceiling_slices(last->front, start, end, v, column - 1);
  744.             last++;
  745.             }
  746.             
  747.         last = save_current;
  748.  
  749.         last_max_floor = max_floor;
  750.         last_min_ceiling = min_ceiling;
  751.         }
  752.  
  753.     save_last = last;
  754.  
  755.  
  756.     // finish up the floors
  757.     while (last->wall != NULL)
  758.         {
  759.         start = MAX(last->bottom, -FIXED_ONE_HALF);
  760.         end = MIN(last->pstart1, FIXED_ZERO);
  761.  
  762.         if (start < end)
  763.             draw_floor_slices(last->front, start, end, v, column - 1);
  764.  
  765.         last++;
  766.         }
  767.  
  768.     // finish up the ceilings
  769.     last = save_last;
  770.     while (last->wall != NULL)
  771.         {
  772.         start = MAX(last->pend2, FIXED_ZERO);
  773.         end = MIN(last->top, FIXED_ONE_HALF);
  774.  
  775.         if (start < end)
  776.             draw_ceiling_slices(last->front, start, end, v, column - 1);
  777.  
  778.         last++;
  779.         }
  780. }
  781.  
  782.  
  783. static void draw_floor_slices(Region *r, fixed start, fixed end, View *v, int column)
  784. {
  785.     int screen_column = view_width - column - 1;
  786.     int start_row, end_row;
  787.     Texture *texture = r->floor_tex;
  788.     fixed height;
  789.     fixed sin_x, cos_x;
  790.  
  791.  
  792.     start_row = FIXED_TO_INT(FIXED_SCALE(start, view_height));
  793.     end_row = FIXED_TO_INT(FIXED_SCALE(end, view_height));
  794.  
  795.     /* Bail out early and save time if there's nothing to draw. */
  796.     if (start_row == end_row)
  797.         return;
  798.  
  799.     start_row = (view_height >> 1) - 1 - start_row;
  800.     end_row = (view_height >> 1) - 1 - end_row;
  801.     if (start_row >= view_height)
  802.         start_row = view_height - 1;
  803.     if (end_row < 0)
  804.         end_row = 0;
  805.  
  806.     height = r->floor - v->height;
  807.     sin_x = view_constants.sin_tab[column];
  808.     cos_x = view_constants.cos_tab[column];
  809.  
  810.  
  811.     while (start_row >= end_row)
  812.         {
  813.         fixed x, dx, y, dy;
  814.         fixed y1;
  815.  
  816.         if (FIXED_ABS(view_constants.row_view[start_row]) < FIXED_EPSILON)
  817.             y1 = FIXED_ONE;
  818.         else
  819.             y1 = fixdiv(height, view_constants.row_view[start_row]) << 4;
  820.  
  821.         x = fixmul(view_constants.view_sin - cos_x, y1) - (v->y << 4);
  822.         y = fixmul(-view_constants.view_cos - sin_x, y1) - (v->x << 4);
  823.         dx = fixmul(view_constants.cos_dx, y1);
  824.         dy = fixmul(view_constants.sin_dx, y1);
  825.  
  826.         if (gTrueColor)
  827.             {
  828.             Pixel16 *fb_byte = fb->pixels16 + fb_rows[start_row] + screen_column;
  829.             draw_floor_slice16(fb_byte, texture->texels16, x, y, dx, dy, texture->log2height, view_width-screen_column);
  830.             }
  831.         else
  832.             {
  833.             Pixel *fb_byte = fb->pixels + fb_rows[start_row] + screen_column;
  834.             draw_floor_slice(fb_byte, texture->texels, x, y, dx, dy, texture->log2height, view_width-screen_column);
  835.             }
  836.             
  837.         start_row--;
  838.         }
  839. }
  840.  
  841.  
  842.  
  843.  
  844. static void draw_ceiling_slices(Region *r, fixed start, fixed end, View *v, int column)
  845. {
  846.     int screen_column = view_width - column - 1;
  847.     int start_row, end_row;
  848.     Texture *texture = r->ceiling_tex;
  849.     fixed height;
  850.     fixed sin_x, cos_x;
  851.  
  852.  
  853.     start_row = FIXED_TO_INT(FIXED_SCALE(start, view_height));
  854.     end_row = FIXED_TO_INT(FIXED_SCALE(end, view_height));
  855.     
  856.     // Bail out early and save time if there's nothing to draw.
  857.     
  858.     if (start_row == end_row)
  859.         return;
  860.  
  861.     start_row = (view_height >> 1) - 1 - start_row;
  862.     end_row = (view_height >> 1) - 1 - end_row;
  863.     if (start_row >= view_height)
  864.         start_row = view_height - 1;
  865.     if (end_row < 0)
  866.         end_row = 0;
  867.  
  868.     height = r->ceiling - v->height;
  869.     sin_x = view_constants.sin_tab[column];
  870.     cos_x = view_constants.cos_tab[column];
  871.  
  872.  
  873.     while (start_row >= end_row)
  874.         {
  875.         fixed x, dx, y, dy;
  876.         fixed y1;
  877.         
  878.  
  879.         if (FIXED_ABS(view_constants.row_view[start_row]) < FIXED_EPSILON)
  880.             y1 = FIXED_ONE;
  881.         else
  882.             y1 = fixdiv(height, view_constants.row_view[start_row]) << 4;
  883.  
  884.         x = fixmul(view_constants.view_sin - cos_x, y1) - (v->y << 4);
  885.         y = fixmul(-view_constants.view_cos - sin_x, y1) - (v->x << 4);
  886.         dx = fixmul(view_constants.cos_dx, y1);
  887.         dy = fixmul(view_constants.sin_dx, y1);
  888.         
  889.         if (gTrueColor)
  890.             {
  891.             Pixel16 *fb_byte = fb->pixels16 + fb_rows[start_row] + screen_column;
  892.             draw_floor_slice16(fb_byte, texture->texels16, x, y, dx, dy, texture->log2height, view_width-screen_column);
  893.             }
  894.         else
  895.             {
  896.             Pixel *fb_byte = fb->pixels + fb_rows[start_row] + screen_column;
  897.             draw_floor_slice(fb_byte, texture->texels, x, y, dx, dy, texture->log2height, view_width-screen_column);
  898.             }
  899.             
  900.         start_row--;
  901.         }
  902. }
  903.  
  904.  
  905. /* Calculate the value of the parameter t at the intersection
  906. **   of the view ray and the wall.  t is 0 at the origin of
  907. **   the wall, and 1 at the other endpoint.
  908. */
  909. static fixed wall_ray_intersection(fixed Vx, fixed Vy, Wall *wall)
  910. {
  911.     fixed denominator, Nx, Ny, Wx, Wy;
  912.      
  913.     Nx = -Vy;
  914.     Ny = Vx;
  915.     Wx = wall->vertex2->tx - wall->vertex1->tx;
  916.     Wy = wall->vertex2->ty - wall->vertex1->ty;
  917.  
  918.     denominator = fixmul(Nx, Wx) + fixmul(Ny, Wy); /* N dot W */
  919.     if (denominator < FIXED_EPSILON)
  920.         return FIXED_ONE - fixdiv(fixmul(Nx, wall->vertex1->tx) +
  921.                                     fixmul(Ny, wall->vertex1->ty), -denominator);
  922.     else if (denominator > FIXED_EPSILON)
  923.         return fixdiv(fixmul(Nx, wall->vertex1->tx) +
  924.                         fixmul(Ny, wall->vertex1->ty), -denominator);
  925.     else
  926.         return FIXED_ZERO;
  927. }
  928.  
  929.  
  930.  
  931.  
  932. /* Calculate values that are dependent only on the screen dimensions and
  933. **   the view.
  934. */
  935. static void calc_view_constants(View *v, short screen_width, short screen_height)
  936. {
  937.     static short last_height = 0, last_width = 0;
  938.     short i;
  939.     fixed x, y;
  940.  
  941.      
  942.     // Make sure that enough memory has been allocated for the tables.
  943.     if (screen_height != last_height)
  944.         {
  945.         if (last_height == 0)
  946.             view_constants.row_view = (fixed *) wtmalloc(screen_height * sizeof(fixed));
  947.         else
  948.             view_constants.row_view = (fixed *) wtrealloc(view_constants.row_view,
  949.                                                              screen_height * sizeof(fixed));
  950.         last_height = screen_height;
  951.         }
  952.         
  953.     if (screen_width != last_width)
  954.         {
  955.         if (last_width == 0)
  956.             {
  957.             view_constants.sin_tab = (fixed *) wtmalloc(screen_width * sizeof(fixed));
  958.             view_constants.cos_tab = (fixed *) wtmalloc(screen_width * sizeof(fixed));
  959.             }
  960.         else
  961.             {
  962.             view_constants.sin_tab = (fixed *)
  963.                         wtrealloc(view_constants.sin_tab, screen_width * sizeof(fixed));
  964.             view_constants.cos_tab = (fixed *)
  965.                         wtrealloc(view_constants.cos_tab, screen_width * sizeof(fixed));
  966.             }
  967.         last_width = screen_width;
  968.         }
  969.       
  970.     view_constants.view_sin = FLOAT_TO_FIXED(sin(- FIXED_TO_FLOAT(v->angle)));
  971.     view_constants.view_cos = FLOAT_TO_FIXED(cos(- FIXED_TO_FLOAT(v->angle)));
  972.     view_constants.screen_dx = fixdiv(FIXED_DOUBLE(v->view_plane_size),
  973.                        INT_TO_FIXED(screen_width));
  974.     view_constants.screen_dy = fixdiv(FIXED_ONE, INT_TO_FIXED(screen_height));
  975.     view_constants.sin_dx = fixmul(view_constants.view_sin, view_constants.screen_dx);
  976.     view_constants.cos_dx = fixmul(view_constants.view_cos, view_constants.screen_dx);
  977.     y = FIXED_SCALE(view_constants.sin_dx, -(screen_width >> 1));
  978.     x = FIXED_SCALE(view_constants.cos_dx, -(screen_width >> 1));
  979.  
  980.     for (i = 0; i < screen_width; i++)
  981.         {
  982.         view_constants.sin_tab[i] = y;
  983.         view_constants.cos_tab[i] = x;
  984.         y += view_constants.sin_dx;
  985.         x += view_constants.cos_dx;
  986.         }
  987.      
  988.     y = FIXED_SCALE(view_constants.screen_dy, screen_height >> 1);
  989.  
  990.     for (i = 0; i < screen_height; i++)
  991.         {
  992.         view_constants.row_view[i] = y;
  993.         y -= view_constants.screen_dy;
  994.         }
  995. }
  996.  
  997.  
  998.  
  999. static void add_objects(World *w, View *v)
  1000. {
  1001.     List *l;
  1002.     fixed view_sin, view_cos;
  1003.  
  1004.  
  1005.     view_sin = view_constants.view_sin;
  1006.     view_cos = view_constants.view_cos;
  1007.  
  1008.     for (l = w->objects; l->next != NULL; l = l->next)
  1009.         {
  1010.         fixed x, y, z;
  1011.         fixed tx, ty;
  1012.         fixed height, width;
  1013.         Object *o = LIST_NODE(l, Object *);
  1014.  
  1015.       
  1016.         /* Skip the object if it is invisible. */
  1017.         if (o->num_images == 0 || o->image[o->cur_image] == NULL)
  1018.             return;
  1019.  
  1020.         /* Convert object coordinates to fixed point and transform. */
  1021.         x = FLOAT_TO_FIXED(o->x) - v->x;
  1022.         y = FLOAT_TO_FIXED(o->y) - v->y;
  1023.         z = FLOAT_TO_FIXED(o->z);
  1024.         height = FLOAT_TO_FIXED(o->height);
  1025.         width  = FLOAT_TO_FIXED(o->xsize);
  1026.         /* Rotate into viewer's coordinate system. */
  1027.         tx = fixmul(x, view_cos) - fixmul(y, view_sin);
  1028.         ty = fixmul(x, view_sin) + fixmul(y, view_cos);
  1029.  
  1030.         /* Only worry about the object if it is in front of the view plane */
  1031.         if (tx > v->eye_distance + FIXED_EPSILON)
  1032.             {
  1033.             int fb1, fb2;
  1034.             fixed pstart, pend;
  1035.             fixed z;
  1036.  
  1037.             /* Project the object onto the view plane . . . */
  1038.             pstart = fixdiv(ty - FIXED_HALF(width), tx);
  1039.             pend   = fixdiv(ty + FIXED_HALF(width), tx);
  1040.  
  1041.             /* Convert to frame buffer coordinates. */
  1042.             pstart = fixdiv(pstart, view_constants.screen_dx + 1);
  1043.             pend   = fixdiv(pend,   view_constants.screen_dx + 1);
  1044.             fb1 = FIXED_TO_INT(pstart) + (view_width >> 1);
  1045.             fb2 = FIXED_TO_INT(pend)   + (view_width >> 1) - 1;
  1046.       
  1047.             if (fb2 >= 0 && fb1 < view_width)
  1048.                 {
  1049.                 Object_start_list *start_list;
  1050.                 Object_end_list   *end_list;
  1051.                 Object_start      *start;
  1052.                 fixed             first_slice = FIXED_ZERO;
  1053.  
  1054.                 z = fixdiv(TO_FIX_2_30(v->eye_distance), tx);
  1055.                 if (fb1 < 0)
  1056.                     {
  1057.                     first_slice = fixdiv(INT_TO_FIXED(-fb1), INT_TO_FIXED(fb2 - fb1));
  1058.                     fb1 = 0;
  1059.                     }
  1060.                 start_list = &obj_start_events[fb1];
  1061.  
  1062.                 if (fb2 >= view_width)
  1063.                     fb2 = view_width - 1;
  1064.                 end_list   = &obj_end_events[fb2];
  1065.  
  1066.                 start = &start_list->events[start_list->n_events];
  1067.                 start->z = z;
  1068.                 start->o = o;
  1069.                 start->first_slice = first_slice;
  1070.                 end_list->events[end_list->n_events] = o;
  1071.  
  1072.                 start_list->n_events++;
  1073.                 end_list->n_events++;
  1074.                 }
  1075.             }
  1076.         }
  1077. }
  1078.  
  1079.  
  1080.  
  1081.  
  1082. /* Insert an object into a depth sorted list. */
  1083. static int add_obj_events(Active_object *active, int n_active, int column)
  1084. {
  1085.     int i, j;
  1086.      
  1087.     for (i = 0; i < obj_start_events[column].n_events; i++)
  1088.         {
  1089.         Object_start *event = obj_start_events[column].events + i;
  1090.         fixed z = event->z;
  1091.         Object *o = event->o;
  1092.  
  1093.         for (j = 0; j < n_active && z < active[j].z; j++);
  1094.       
  1095.         memmove(active + j + 1, active + j, sizeof(Active_object) * (n_active - j));
  1096.         active[j].z = z;
  1097.         active[j].o = o;
  1098.         if (event->first_slice == FIXED_ZERO)
  1099.             active[j].x = FIXED_ZERO;
  1100.         else
  1101.             active[j].x = FIXED_SCALE(event->first_slice, o->image[o->cur_image]->width);
  1102.             
  1103.         active[j].dx = fixdiv(INT_TO_FIXED(o->image[o->cur_image]->width << 1),
  1104.                 fixmul(FLOAT_TO_FIXED(o->xsize), FIXED_SCALE(FROM_FIX_2_30(z), view_width)));
  1105.       
  1106.         n_active++;
  1107.         }
  1108.       
  1109.     return n_active;
  1110. }
  1111.  
  1112.  
  1113.  
  1114. static int remove_obj_events(Active_object *active, int n_active, int column)
  1115. {
  1116.     int i, j;
  1117.     Object *o;
  1118.  
  1119.  
  1120.     /* This is really inefficient, so I hope these event lists are small. */
  1121.     for (i = 0; i < obj_end_events[column].n_events; i++)
  1122.         {
  1123.         o = obj_end_events[column].events[i];
  1124.  
  1125.         for (j = 0; j < n_active && active[j].o != o; j++);
  1126.         n_active--;
  1127.         memmove(active + j, active + j + 1, sizeof(Active_object) * (n_active - j));
  1128.         }
  1129.  
  1130.     return n_active;
  1131. }
  1132.  
  1133.  
  1134.  
  1135.  
  1136. /**********************************************************************
  1137. **
  1138. ** This section contains the guts of the wall drawing functions.  There
  1139. **   are a number of static variables declared here which are used to pass
  1140. **   information between these functions.  They are not used anyplace else.
  1141. **   If only C had a block structure like Pascal...
  1142. */
  1143.  
  1144. static fixed pstart1, pend1, pstart2, pend2;
  1145. static fixed top, bottom;
  1146. Region *front, *back;
  1147.  
  1148.  
  1149. /* Walls can have up to two segments--one attached to the floor and one
  1150. **   attached to the ceiling.
  1151. */
  1152. inline void draw_wall_segment(fixed pstart, fixed pend,
  1153.                                   fixed start,
  1154.                                   fixed z,
  1155.                                   fixed height,
  1156.                                  int fb_column,
  1157.                                   void *tex_base,
  1158.                                  Wall *wall,
  1159.                                 fixed tex_dy)
  1160. {
  1161.     int fb_start, fb_end;
  1162.     fixed tex_y;
  1163.  
  1164.  
  1165.     // Clip the wall slice.
  1166.  
  1167.     if (pstart < bottom)
  1168.         {
  1169.         pstart = bottom;
  1170.         start = fixdiv(pstart, z) + height;
  1171.         }
  1172.         
  1173.     if (pend >= top)
  1174.         pend = top - 1;
  1175.  
  1176.     fb_start = (view_height >> 1) - 1 - FIXED_TO_INT(FIXED_SCALE(pstart, view_height));
  1177.     fb_end   = (view_height >> 1) - 1 - FIXED_TO_INT(FIXED_SCALE(pend, view_height));
  1178.  
  1179.     fb_column = view_width - fb_column - 1;
  1180.     
  1181.     if (wall->sky)
  1182.         tex_y = fixmul(view_constants.row_view[fb_start], wall->yscale) + wall->yphase;
  1183.     else
  1184.         tex_y = fixmul(start, wall->yscale) + wall->yphase;
  1185.  
  1186.     if (gTrueColor)
  1187.         {
  1188.         Pixel16 *fb_byte   = fb->pixels16 + fb_column + fb_rows[fb_start];
  1189.         Pixel16 *last_byte = fb->pixels16 + fb_column + fb_rows[fb_end];
  1190.         
  1191.         if (wall->opaque)
  1192.             draw_wall_slice16(fb_byte, last_byte, (Pixel16 *)tex_base, tex_y, tex_dy,
  1193.                               view_width, 16 - wall->surface_texture->log2height);
  1194.         else
  1195.             draw_transparent_slice16(fb_byte, last_byte, (Pixel16 *)tex_base, tex_y, tex_dy,
  1196.                             view_width, 16 - wall->surface_texture->log2height);
  1197.         }
  1198.     else
  1199.         {
  1200.         Pixel *fb_byte = fb->pixels + fb_column + fb_rows[fb_start];
  1201.         Pixel *last_byte = fb->pixels + fb_column + fb_rows[fb_end];
  1202.  
  1203.         if (wall->opaque)
  1204.             draw_wall_slice(fb_byte, last_byte, (Pixel *)tex_base, tex_y, tex_dy,
  1205.                               view_width, 16 - wall->surface_texture->log2height);
  1206.         else
  1207.             draw_transparent_slice(fb_byte, last_byte, (Pixel *)tex_base, tex_y, tex_dy,
  1208.                              view_width, 16 - wall->surface_texture->log2height);
  1209.         }
  1210. }
  1211.  
  1212.  
  1213. inline void draw_wall(Wall *wall,
  1214.               fixed z,
  1215.               fixed Vx, fixed Vy,
  1216.               View *v,
  1217.               int column)
  1218. {
  1219.     fixed tex_dy;
  1220.     int tex_column;
  1221.     Boolean do_floor, do_ceiling;
  1222.     Texture *texture = wall->surface_texture;
  1223.     fixed start1, start2;
  1224.     fixed t;
  1225.  
  1226.  
  1227.     start1 = front->floor;
  1228.     start2 = back->ceiling;
  1229.  
  1230.     if (pend1 > pend2)
  1231.         pend1 = pend2;
  1232.     if (pstart2 < pstart1)
  1233.         pstart2 = pstart1;
  1234.  
  1235.     texture = wall->surface_texture;
  1236.     do_floor = (pstart1 < top) && (pend1 > bottom) && (pend1 - pstart1 > FIXED_EPSILON);
  1237.     do_ceiling = (pstart2 < top) && (pend2 > bottom) && (pend2 - pstart2 > FIXED_EPSILON);
  1238.       
  1239.     // Don't do anything more with this wall if there's nothing to draw.
  1240.  
  1241.     if (!do_floor && !do_ceiling)
  1242.         return;
  1243.  
  1244.     /* We compute the texture coordinates for sky walls and normal walls
  1245.     **   in fundamentally different ways.
  1246.     */
  1247.     if (wall->sky)
  1248.         {
  1249.         fixed angle;
  1250.  
  1251.         /* Compute the angle of this column.  We'll use the angle
  1252.         **   exclusively to determine which texture column to
  1253.         **   display for this slice of sky.
  1254.         */
  1255.         angle = v->angle + fixdiv(FIXED_SCALE(v->arc, column - (view_width >> 1)),
  1256.                     INT_TO_FIXED(view_width));
  1257.         angle -= FIXED_SCALE(FIXED_2PI, FIXED_TO_INT(fixdiv(angle, FIXED_2PI)));
  1258.         angle = fixdiv(angle, FIXED_2PI);
  1259.         if (angle < FIXED_ZERO)
  1260.             angle = FIXED_ONE - angle;
  1261.         tex_column = FIXED_TO_INT(fixmul(angle, wall->xscale)) & (texture->width - 1);
  1262.         tex_dy = fixdiv(wall->yscale, INT_TO_FIXED(view_height));
  1263.         }
  1264.     else
  1265.         {
  1266.         t = wall_ray_intersection(Vx, Vy, wall);
  1267.         /* From t, calculate the integer coordinates in the texture
  1268.         **   bitmap.  For efficiency, we assume that the width of the
  1269.         **   texture is a power of two.
  1270.         */
  1271.         tex_column = FIXED_TO_INT(wall->xphase + fixmul(t, wall->xscale)) &
  1272.                            (texture->width - 1);
  1273.         /* Test to avoid overflow here . . .  if the wall is so far
  1274.         **   away that z (which is 1 / distance) is less than
  1275.         **   FIXED_EPSILON, then it will be so small when rendered
  1276.         **   that we can use a bogus value for tex_dy.
  1277.         */
  1278.         if (z < FIXED_EPSILON)
  1279.             tex_dy = 0;
  1280.         else
  1281.             tex_dy = fixdiv(wall->yscale, FIXED_SCALE(z, view_height));
  1282.         }
  1283.     
  1284.     if (gTrueColor)
  1285.         {
  1286.         Pixel16 *tex_base = TEXTURE_COLUMN16(texture, tex_column);
  1287.  
  1288.         if (do_floor)
  1289.             draw_wall_segment(pstart1, pend1, start1, z, v->height, column, tex_base, wall, tex_dy);
  1290.  
  1291.         if (do_ceiling)
  1292.             draw_wall_segment(pstart2, pend2, start2, z, v->height, column, tex_base, wall, tex_dy);
  1293.         }
  1294.     else
  1295.         {
  1296.         Pixel *tex_base = TEXTURE_COLUMN(texture, tex_column);
  1297.  
  1298.         if (do_floor)
  1299.             draw_wall_segment(pstart1, pend1, start1, z, v->height, column, tex_base, wall, tex_dy);
  1300.  
  1301.         if (do_ceiling)
  1302.             draw_wall_segment(pstart2, pend2, start2, z, v->height, column, tex_base, wall, tex_dy);
  1303.         }
  1304. }
  1305.  
  1306.  
  1307.  
  1308. inline void draw_object(Object *o, fixed z, int tex_column, View *v, int fb_column)
  1309. {
  1310.     fixed    pstart, pend;
  1311.     fixed    tex_y, tex_dy;
  1312.     int        fb_start, fb_end;
  1313.     fixed    obj_height = FLOAT_TO_FIXED(o->height);
  1314.      
  1315.  
  1316.     if (!o->num_images) return;
  1317.     
  1318.     // Project the bottom and top of the object onto the slice.
  1319.      
  1320.     pstart = fixmul(z, FLOAT_TO_FIXED(o->z) - v->height);
  1321.     pend   = fixmul(z, obj_height) + pstart;
  1322.      
  1323.     // See if the object is visible in this column.
  1324.     if (pstart > top || pend < bottom || pend - pstart < FIXED_EPSILON)
  1325.         return;
  1326.  
  1327.     tex_dy = fixdiv(INT_TO_FIXED(o->image[o->cur_image]->height), FIXED_SCALE(pend - pstart, view_height));
  1328.  
  1329.     // Clip the object slice.
  1330.     
  1331.     if (pstart < bottom)
  1332.         {
  1333.         tex_y = fixmul(bottom - pstart, FIXED_SCALE(tex_dy, view_height));
  1334.         pstart = bottom;
  1335.         }
  1336.     else
  1337.         tex_y = FIXED_ZERO;
  1338.         
  1339.     if (pend > top)
  1340.         pend = top;
  1341.  
  1342.     fb_start = (view_height >> 1) - 1 - FIXED_TO_INT(FIXED_SCALE(pstart, view_height));
  1343.     fb_end   = (view_height >> 1) - 1 - FIXED_TO_INT(FIXED_SCALE(pend, view_height));
  1344.     fb_column = view_width - fb_column - 1;
  1345.     
  1346.     if (gTrueColor)
  1347.         {
  1348.         Pixel16    *fb_byte = fb->pixels16 + fb_column + fb_rows[fb_start];
  1349.         Pixel16    *last_byte = fb->pixels16 + fb_column + fb_rows[fb_end];
  1350.         Pixel16    *tex_base = TEXTURE_COLUMN16(o->image[o->cur_image], tex_column);
  1351.  
  1352.         draw_transparent_slice16(fb_byte, last_byte, tex_base, tex_y, tex_dy, view_width,
  1353.                                     16 - o->image[o->cur_image]->log2height);
  1354.  
  1355.         }
  1356.     else
  1357.         {
  1358.         Pixel    *fb_byte = fb->pixels + fb_column + fb_rows[fb_start];
  1359.         Pixel    *last_byte = fb->pixels + fb_column + fb_rows[fb_end];
  1360.         Pixel    *tex_base = TEXTURE_COLUMN(o->image[o->cur_image], tex_column);
  1361.         
  1362.         draw_transparent_slice(fb_byte, last_byte, tex_base, tex_y, tex_dy, view_width,
  1363.                                 16 - o->image[o->cur_image]->log2height);
  1364.         }    
  1365. }
  1366.  
  1367.  
  1368. typedef struct {
  1369.      fixed top, bottom;
  1370.      Active_wall *active;
  1371.      Active_object *active_obj;
  1372. } Saved_wall;
  1373.  
  1374. #define MAX_TRANSPARENT_WALLS 100
  1375.  
  1376. Saved_wall transparent_walls[MAX_TRANSPARENT_WALLS];
  1377.  
  1378.  
  1379. /* do_walls() draws all the walls, floors, and ceilings for a screen column. */
  1380. static void do_walls(Active_wall *active, int n_active, Active_object *active_obj,
  1381.                         int n_active_obj, int column, View *v, fixed Vx, fixed Vy)
  1382. {
  1383.     fixed height = v->height;
  1384.     Saved_wall *last_saved = transparent_walls;
  1385.  
  1386.  
  1387.      /* As we walk front to back through the active wall list, we track
  1388.      **   the top and bottom of the view port for this column.  Because of
  1389.      **   the restrictions placed on world geometry, the view port will
  1390.      **   always be a single interval, making clipping extremely simple.
  1391.      **   When bottom is greater than top, the view port is closed--nothing
  1392.      **   behind the current wall will be visible.
  1393.      */
  1394.     top    = FIXED_ONE_HALF;
  1395.     bottom = -FIXED_ONE_HALF;
  1396.  
  1397.      /* This loop moves from front to back through the list of 'active'
  1398.      **   walls.  We stop when we reach the last wall in the list, or
  1399.      **   when the walls we've already looked at completely obscure anything
  1400.      **   behind them.
  1401.      */
  1402.     while (n_active-- > 0 && bottom < top)
  1403.         {
  1404.         Wall *wall = active->wall;
  1405.         fixed z = active->z;
  1406.         fixed dz = active->dz;
  1407.  
  1408.  
  1409.         /* See if there are any objects in front of this wall which need
  1410.         **   to be drawn.  Since objects have transparent parts, drawing 
  1411.         **   them must be deferred until after the opaque wall slices have
  1412.         **   been drawn.  Transparent walls are handled in a similar
  1413.         **   manner later on in the loop.
  1414.         */
  1415.         while (n_active_obj > 0 && active_obj->z >= z)
  1416.             {
  1417.             /* Record the object in the save buffer. */
  1418.             last_saved->top = top;
  1419.             last_saved->bottom = bottom;
  1420.             last_saved->active_obj = active_obj;
  1421.             last_saved->active = NULL;
  1422.             last_saved++;
  1423.  
  1424.                /* Advance through the object list. */
  1425.             n_active_obj--;
  1426.             active_obj++;
  1427.             }
  1428.  
  1429.  
  1430.         /* Set up the front and back region pointers--if we're behind
  1431.         **   a wall, these need to be reversed.
  1432.         */
  1433.         if (active->is_back_view)
  1434.             {
  1435.             front = wall->back;
  1436.             back = wall->front;
  1437.             }
  1438.         else
  1439.             {
  1440.             front = wall->front;
  1441.             back = wall->back;
  1442.             }
  1443.  
  1444.         /* If this wall has not been visible before, set the visible flag 
  1445.         **   and set up the projected coordinates and deltas.
  1446.         */
  1447.         if (!active->visible)
  1448.             {
  1449.             active->pstart1 = fixmul2_30(TO_FIX_8_24(front->floor - height), z);
  1450.             active->pend1 = fixmul2_30(TO_FIX_8_24(back->floor - height), z);
  1451.             active->pstart2 = fixmul2_30(TO_FIX_8_24(back->ceiling - height), z);
  1452.             active->pend2 = fixmul2_30(TO_FIX_8_24(front->ceiling - height), z);
  1453.             active->dpstart1 = fixmul2_30(TO_FIX_8_24(front->floor - height), dz);
  1454.             active->dpend1 = fixmul2_30(TO_FIX_8_24(back->floor - height), dz);
  1455.             active->dpstart2 = fixmul2_30(TO_FIX_8_24(back->ceiling - height), dz);
  1456.             active->dpend2 = fixmul2_30(TO_FIX_8_24(front->ceiling - height), dz);
  1457.             active->visible = TRUE;
  1458.             }
  1459.             
  1460.         cur_slice->pstart1 = FROM_FIX_8_24(active->pstart1);
  1461.         cur_slice->pend1 = FROM_FIX_8_24(active->pend1);
  1462.         cur_slice->pstart2 = FROM_FIX_8_24(active->pstart2);
  1463.         cur_slice->pend2 = FROM_FIX_8_24(active->pend2);
  1464.         
  1465.         if (active->is_back_view)
  1466.             {
  1467.             cur_slice->front = wall->back;
  1468.             cur_slice->back = wall->front;
  1469.             cur_slice->pstart1 = cur_slice->pend1;
  1470.             cur_slice->pend2 = cur_slice->pstart2;
  1471.             }
  1472.         else
  1473.             {
  1474.             cur_slice->front = wall->front;
  1475.             cur_slice->back = wall->back;
  1476.             }
  1477.  
  1478.         cur_slice->top = top;
  1479.         cur_slice->bottom = bottom;
  1480.         cur_slice->wall = wall;
  1481.         cur_slice->z = FROM_FIX_2_30(z);
  1482.         cur_slice->is_back_view = active->is_back_view;
  1483.  
  1484.         /* If this wall is opaque, we draw it now and adjust bottom
  1485.         **   and top appropriately.  Otherwise, we defer the drawing of
  1486.         **   the wall slice until later.
  1487.         */
  1488.         
  1489.         if (active->wall->opaque)
  1490.             {
  1491.             pstart1 = FROM_FIX_8_24(active->pstart1);
  1492.             pend1 = FROM_FIX_8_24(active->pend1);
  1493.             pstart2 = FROM_FIX_8_24(active->pstart2);
  1494.             pend2 = FROM_FIX_8_24(active->pend2);
  1495.  
  1496.             draw_wall(wall, FROM_FIX_2_30(z), Vx, Vy, v, column);
  1497.  
  1498.             if (bottom < pend1)
  1499.                 bottom = pend1;
  1500.             if (bottom < pstart1)
  1501.                 bottom = pstart1;
  1502.             if (top > pstart2)
  1503.                 top = pstart2;
  1504.             if (top > pend2)
  1505.                 top = pend2;
  1506.             }
  1507.         else
  1508.             {
  1509.             last_saved->top        = top;
  1510.             last_saved->bottom     = bottom;
  1511.             last_saved->active     = active;
  1512.             last_saved->active_obj = NULL;
  1513.             last_saved++;
  1514.             }
  1515.     
  1516.         active++;
  1517.         cur_slice++;
  1518.         }
  1519.         
  1520.      // place the 'end of column' sentinel
  1521.      
  1522.     cur_slice->wall = NULL;
  1523.     cur_slice->top = top;
  1524.     cur_slice->bottom = bottom;
  1525.  
  1526.     cur_slice++;
  1527.     
  1528.     // Draw floor & ceilings here
  1529.     
  1530.     //draw_floors(intersections, v, column);    // Someday, anyway
  1531.     
  1532.     // End floors & ceilings
  1533.  
  1534.     /* Now, handle the objects and transparent walls.  last_saved points
  1535.     **   to an entry in the saved walls buffer.  Each entry consists of the
  1536.     **   the active list entry plus the top and bottom clipping info.
  1537.     */
  1538.     
  1539.     while (last_saved > transparent_walls)
  1540.         {
  1541.         Active_wall *active;
  1542.         Active_object *active_obj;
  1543.  
  1544.  
  1545.         last_saved--;
  1546.  
  1547.         top = last_saved->top;
  1548.         bottom = last_saved->bottom;
  1549.  
  1550.         active = last_saved->active;
  1551.  
  1552.         /* If active is not NULL, this entry is a wall;  if it is NULL,
  1553.         **    this entry is an object and active_obj is not null.
  1554.         */
  1555.         
  1556.         if (active != NULL)
  1557.             {
  1558.             pstart1 = FROM_FIX_8_24(active->pstart1);
  1559.             pend1   = FROM_FIX_8_24(active->pend1);
  1560.             pstart2 = FROM_FIX_8_24(active->pstart2);
  1561.             pend2   = FROM_FIX_8_24(active->pend2);
  1562.  
  1563.             draw_wall(active->wall, FROM_FIX_2_30(active->z), Vx, Vy, v, column);
  1564.             }
  1565.         else
  1566.             {
  1567.             active_obj = last_saved->active_obj;
  1568.             draw_object(active_obj->o, FROM_FIX_2_30(active_obj->z),
  1569.                            FIXED_TO_INT(active_obj->x), v, column);
  1570.             }
  1571.         }
  1572. }
  1573.  
  1574.  
  1575.